
<TITLE>prob006: Golomb rulers</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob006: Golomb rulers</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.ualberta.ca/~vanbeek">
          <B>Peter van Beek</B></A>
          <ADDRESS><a href="mailto:vanbeek@cs.ualberta.ca">
          vanbeek@cs.ualberta.ca</a></ADDRESS>
</TABLE>
</CENTER>

<HR><!------------------------------------------------------------------------>
<H3> Results </H3>

<P>
Optimal Golomb rulers have been found for rulers with
up to 21 marks and non-optimal rulers are known for
rulers with up to 150 marks, all found using specialized programs.

<P>
Tables showing the current best Golomb rulers can be found at:

	<UL>
	<P>
	<LI>
	<A HREF="http://members.aol.com/golomb20/">
	Internet project for finding optimal Golomb rulers</A>
	<P>
	<LI>
	<A HREF="http://www.research.ibm.com/people/s/shearer/grule.html">
	James B. Shearer's Golomb ruler page</A>
	</UL>

<P>
My experience with these
problems suggests that even quite small
problems (fewer than fifteen marks) are very difficult
for complete methods such as backtracking search. The difficulty
lies in both proving optimality and in finding a solution (since
the problems have either a unique solution or just a handful
of solutions).

<P>
Jean-Francois Puget reports finding a solution
for a 12 mark rule with ILOG Solver 
after 2042000 backtracks.
The total number of backtracks including the proof of
optimality is 3143316. A 13 mark ruler was 
found after 156478 seconds on a sparc 20 and more than 
26969000 backtracks. Finding the solution and
proving optimality took
53108352 backtracks and 330643 seconds on a sparc 20
(almost 4 days). 


<P>
<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.

